package com.lw.leetcode.sort.b;

import java.util.ArrayList;
import java.util.List;

/**
 * 969. 煎饼排序
 *
 * @Author liw
 * @Date 2021/6/21 16:34
 * @Version 1.0
 */
public class PancakeSort {

    public static void main(String[] args) {
        PancakeSort test = new PancakeSort();

        int[] arr = {3, 2, 4, 1};
//        int[] arr = {1};
        List<Integer> integers = test.pancakeSort(arr);
        System.out.println(integers);
    }

    public List<Integer> pancakeSort(int[] arr) {
        int length = arr.length;
        List<Integer> list = new ArrayList<>(length);
        int max = length;
        while (true) {
            for (int i = 0; i < length; i++) {
                if (arr[i] == max) {
                    if (i == --max) {
                        continue;
                    }
                    int st = 0;
                    int end = i;
                    if (st < end) {
                        list.add(i + 1);
                    }
                    while (st < end) {
                        int item = arr[st];
                        arr[st++] = arr[end];
                        arr[end--] = item;
                    }
                    st = 0;
                    end = max;
                    while (st < end) {
                        int item = arr[st];
                        arr[st++] = arr[end];
                        arr[end--] = item;
                    }
                    list.add(max + 1);
                }
            }
            if (max == 0) {
                break;
            }
        }
        return list;
    }
}
